package com.xuhj.array;

import java.lang.reflect.Array;
import java.util.Arrays;

/*
 * @Author xuhj
 * @Description https://leetcode-cn.com/problems/kth-missing-positive-number/
 * @Date 10:23 下午 2022/1/20
 * @Param
 * @return
 **/
public class Leetcode_1539 {
    public static void main(String[] args) {
        System.out.println(findKthPosition(new int[]{2, 3, 4, 7, 11}, 5));

    }
    public static Integer findKthPosition(int[] inputArr,int k){
        //数组第一个数字为1
        int currPositionValue = 1;
        int i = 0;
        while(i < inputArr.length){
            if(currPositionValue < inputArr[i]){
                k--;
                if(k == 0){
                    return currPositionValue;
                }
                currPositionValue++;
            }else {
                currPositionValue++;
                i++;
            }
        }
        return currPositionValue - k + 1;
    }
}

/**
 * 题目描述：
 * 给你一个 严格升序排列 的正整数数组 arr 和一个整数 k
 * 请你找到这个数组里第 k 个缺失的正整数。
 * e.g.
 *【
 * 输入：arr = [2,3,4,7,11], k = 5
 * 输出：9
 * 解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9
 * 】
 * 【
 * 输入：arr = [1,2,3,4], k = 2
 * 输出：6
 * 解释：缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。
 * 】
 *
 * 题解：
 * 使用 cur 表示当前位置应该出现的数，如果数组中该位置上的数和 cur 不相等，说明 cur 缺失了，就将 k - 1，并且把 cur + 1，因为刚刚那个缺失的 cur 已经计算过了。接着，我们再来看数组中这个位置上的数是不是 cur + 1，如果还不是，那继续 k - 1，cur + 1；如果是，说明 cur + 1 出现了即没有缺失，那我们就判断数组的下一位是不是 cur + 2 ......
 * 最后可能会有一种情况，那就是数组已经遍历完了但是 k 还没有减到 0，这就说明缺失的第 k 个数是超过数组的最后一个数的，这里我们需要做个特殊处理，其实就是 (数组的最后一个数 - 1) + 剩余的 k 值 即可
 * */